A topic of widespread interest is the design of a high-capacity wide-coverage controllable and scalable data network. The need for consumption and exchange of information is evidenced by the popularity of the Internet. The demand for information distribution is likely to increase significantly as a result of future network performance improvements. Also, it can be argued that there is a suppressed demand for new services and information transfer at a much higher rate than what today's multi-terabits per second Internet can bear. It is widely accepted that the Next-Generation Internet will be structured using an optical-core interconnecting electronic edge nodes, such as intelligent routers.
A brief description of conventional network architecture and adaptive network reconfiguration is provided below. FIG. 1 illustrates a data network 100 having a large number, possibly several thousands, of edge nodes 120, with each edge node comprising a source node, to be referenced as 120A, and a sink node, to be referenced as 120B. The source node 120A and the sink node 120B of an edge node 120 share memory and control. Where a distinction between the source-node part 120A and the sink-node part 120B of an edge node is not necessary, either may be referenced simply as an edge node 120. The edge nodes 120 may be interconnected through a core stage that comprises at least one core node 140. An edge node that establishes a path through a core node is said to subtend to the core node. An edge node may subtend to some or all of the core nodes 140 of a network 100. When an edge node subtends to two or more core nodes, it selects a core node 140 to establish a path to a given destination edge node according to some merit criterion, such as propagation delay. The edge nodes sending data traffic through a core node are said to be subtending edge nodes of the core node. The edge nodes 120 may, in addition, be interconnected directly by links of static capacity. The capacity of the network is determined by the capacities of the edge nodes 120 and the core nodes 140. The links interconnecting the edge nodes to core nodes or to other edge nodes are preferably wavelength division multiplexed (WDM) links. In the network of FIG. 1, a link from a source node 120A to a core node 140 is hereinafter called an upstream link and a link from a core node to a sink node 120B is called a downstream link. A channel in an upstream link is called an upstream channel and a channel in a downstream link is called a downstream channel.
Reconfiguration of a core node, that receives requests from subtending source nodes to increase path capacities to specified destination sink nodes, generally requires that the core node ensure the availability of sufficient uncommitted capacity to each destination sink node specified in the requests. The admission of a capacity-increase request is determined according to one of two admission policies. According to the first admission policy, the core node ensures the availability of sufficient capacity on the downstream link to a destination sink node but need not consult the sink node. According to the second admission policy, the destination sink node must be consulted. The term ‘reconfiguration latency’ of an edge node 120 with respect to a given core node 140 is defined herein as the minimum time required to realize a path-capacity-increment request that has been accepted by an admission control process. The reconfiguration latency of an edge node with respect to a core node can be selected as the sum of the interval of time, E1, required by a core-node controller to compute a reconfiguration schedule, and an interval of time, E2, determined as the total of the round-trip propagation delay between the edge node 120 and the core node 140 and the time required by the edge node to modify its internal switching pattern to correspond to a new schedule that the edge node receives from the core node. Alternatively, the reconfiguration latency can be defined as the larger of E2 and E2. The use of the former selection, i.e., the sum of E2 and E2, simplifies time coordination. The term “configuration period” refers to the interval between successive reconfigurations of a core node. The configuration period, with respect to a given core node, must at least equal the largest reconfiguration latency for all edge nodes subtending to the core node.
FIG. 2 illustrates the main components of an edge node 120 of FIG. 1 which participate in the scheduling process in preparation for a reconfiguration. An edge node controller 210 exchanges control signals with a plurality of input-port controllers 220 and a plurality of output-port controllers 230. The edge controller 210 computes a data-transfer schedule and communicates the schedule to the input-port controllers 220 which controls the transfer of data from input ports (not illustrated in FIG. 2) to output ports (not illustrated) through a switching fabric 240 according to the schedule. This enables contention-free transfer of data from the input ports to the output ports of the edge node. The input-port controllers 220 and the output-port controllers 230 may exchange control data directly through an inter-port link 250. Alternatively, the edge controller 210, the input port controllers 220 and the output port controllers 230 may exchange control data over one or more communication buses (not illustrated) provided within the edge node 120.
The switching fabric 240 need not be symmetrical, i.e., the number of input ports need not equal the number of output ports. The inequality can be adapted to traffic distribution, traffic asymmetry, and multi-casting wherein a data stream from a single source is sent to multiple sinks.
To handle traffic of diverse characteristics, several switching modes can coexist in the same network. These switching modes may include link-switching, channel-band switching, single-channel switching, time division multiplexed (TDM) switching, and burst-switching.
The network control is preferably exercised primarily at the edge nodes 120. A simple core structure is essential for realizing a high-capacity high performance network in which the core connectivity can be adapted according to spatial traffic variation, thus yielding an agile network. In an agile network, time locking of edge nodes 120 to core nodes 140 is generally required to enable adaptive reconfiguration. Time locking enables time coordination of the switching functions at the edge nodes 120 and core nodes 140. Without time locking, a large time guard, of the order of several milliseconds, would be needed between successive configuration updates. Even without reconfiguration, time locking is required in the TDM mode to align the time frames at the input ports of each bufferless core node, and in the burst-switching mode to enable efficient burst transfer across the core node. This process of time-coordination is detailed in Applicant's copending U.S. patent application, Ser. No. 10/054,509, filed on Nov. 13, 2001 and titled “Time-Coordination in a Burst-Switching Network”.
A parameter of interest in network design is the adjacency of an edge node, which is defined herein as the number of sink nodes that a source node can reach directly or through the network core without switching at an intermediate edge node. In the case where the adjacency is less than the number of sink nodes, the sink nodes that cannot be reached directly from a source node through the core can be reached through tandem switching at intermediate edge nodes. This generally requires that the source node and sink node of each intermediate edge node share the same data memory, which is a common practice in the art.
Switching Mode and Granularity
A network may provide different switching granularities associated with different switching modes including link switching, channel-band switching, single-channel switching, TDM switching, and burst switching.
In the link-switching mode, the entire signal in any of the fiber links from a source node is switched in the core. The core does not inspect the signal carried by any fiber link. It simply directs the link's signal from one fiber link to another. Due to this very coarse granularity, a source node having L upstream fiber links can reach at most L sink nodes.
In the channel-band switching mode, instead of switching the entire signal of a fiber link in unison, the signals in selected channel bands (wavelength bands) can be switched from a source node to a sink node. If the wavelength channels in a link are grouped into B channel bands, then the total number of channel bands from the source node to the core is L×B, which is also the adjacency of the source node.
In the single-channel switching mode, each wavelength channel can be routed independently leading to an adjacency of L×W, where W is the number of wavelength channels carried by a fiber link. This increases the required control effort at the core nodes but reduces the mean number of hops per traffic stream.
In the TDM switching mode, which requires fast-switching core nodes, the data carried on each channel (wavelength) can be organized in a repetitive TDM frame having a predefined number of time slots with a predefined length (bytes) for each time slot. Each time slot has a spatial attribute, typically a data-stream identifier. A data stream is normally defined by its source node, sink node, and a designated network path. A time slot can also be unused, having a null attribute. A TDM frame is used repetitively, but the spatial attributes of some or all of the time slots can change with time. The increased adjacency realized by the use of TDM can eliminate, or significantly reduce, the need for tandem switching through intermediate edge nodes.
FIG. 3 illustrates a reconfiguration process of a TDM core node where, at an input port of a switching fabric of a core node 140, a TDM frame 320 of 16 time slots contains data destined to five output ports labeled A to E with corresponding time-slot allocations per TDM frame of 2, 3, 5, 2, and, 4 respectively. After reconfiguration, the numbers of time-slot allocations to the five output ports, in TDM frame 340, change to 3, 4, 4, 5, and 0, respectively. The time slots allocated for a given output port are preferably evenly spaced in the TDM frame.
In the TDM case, each source node can allocate time slots to any sink node in any of its channels during each TDM frame period. The number of time slots per TDM frame allocated by a source node to any sink node is determined and rounded-up to the nearest integer. The core directs the data in each time slot to an associated destination sink node. Each core node is made aware of the spatial attributes of each time slot in the time-slotted frame in each channel to which it is connected. Suppose a source node has L×W channels connected to the core. If each time frame has S time slots, then the data transferred from a source node to the sink nodes would be segmented in L×W×S time slots for each TDM frame period. These time slots are totally independent, in the sense that each can be routed independently. Thus, the adjacency of a source node can be increased significantly. For example, if L=8, W=40, and S=256, then the data within each of 81920 time slots can be switched independently to different destinations. If the number, N, of edge nodes (sink nodes) is only 2000, for example, then the ratio of the number of time slots to the number of edge nodes is more than 40, and the adjacency of each source node is, therefore, the entire network.
In the burst-switching mode, data bursts of variable sizes are transferred from source to sink. Burst switching is a form of packet switching in which the packet size is sufficiently large to deserve a better treatment than what a packet gets in current IP networks. Burst switching requires fast switching elements in the core. A detailed description of burst switching is given in the aforementioned U.S. patent application, Ser. No. 10/054,509, titled “Time-Coordination in a Burst-Switching Network”.
Time coordination is critical in the TDM mode in order to align the time frames at each bufferless core node, and in the burst-switching mode to allow uninterrupted transfer of bursts.
Time coordination, as will be detailed below, is feasible only between a core node and its subtending edge nodes.
Individual Connection Admission Versus Core Reconfiguration
An alternative to individual-connection setup is to setup paths of adaptive capacity for pairs of edge nodes. Establishing paths of adaptive capacity for edge-node pairs offers the advantage of fast connection setup because the admission of a connection is determined only by the respective source node and sink node. With a sink node having a high-capacity data buffer, the connection admission may be determined solely by the source node. To realize simple connection setup without adversely affecting network efficiency, the edge-to-edge paths may adapt their capacities to time-varying traffic levels. The path-capacity unit can be a wavelength channel (typically modulated at 10 Gb/s) in channel switching or a time-slot in a wavelength channel in TDM switching. The latter requires fast-switching core nodes as mentioned earlier.
An agile network is characterized as a network that has paths of adaptive capacities from source nodes to respective sink nodes. The capacity of a path is determined as a number of channels, for channel-switched paths, or a number of time-slots per TDM frame, if channels are time shared and switched in the TDM mode.
Accepting a connection requires examining a route set and selecting a route having a sufficient free capacity. A route set comprises selected candidate routes for an edge-node pair. The capacities of already established paths are adapted to traffic variation. The capacity of a path can be increased by signaling to gain admission from each node along the path. A path-capacity decrement is also signaled so that the nodes along the path can release committed capacity.
In a conventional scheme of establishing new paths, or modifying the capacities of existing paths, requests for capacity modification are processed one at a time. During the connection-setup time, resources are held in an idle state until the respective source node is given permission to start data transmission. The connection-setup period includes round-trip propagation delay and processing delay along intermediate nodes. If the mean holding time of a connection is relatively small, i.e., if connections are created frequently, or their capacity allocations are modified frequently, the idle time of transmission-links can be relatively significant. For example, if connections are created or modified every one second, a setup period of 100 milliseconds, for example, results in a relative capacity loss of 0.1. In addition, in an admission system based on individual connection setup, a significant mean vacancy of transmission links is required to reduce connection-request blocking.
In another scheme, requests for establishing new paths or capacity modification of existing paths are processed periodically where a core node can be reconfigured at designated instants, and each respective edge node is reconfigured at an instant that is determined to suit the core-configuration time. The minimum interval between successive reconfigurations is dictated primarily by the round-trip delay between a core node and the edge nodes. In a network of wide coverage, the round-trip delay between a core node and its adjacent edge nodes can vary significantly, for example between a fraction of a millisecond and a hundred milliseconds. Scheduling the reconfiguration of a core node to suit the highest round-trip delay can result in reduced network agility.
Therefore, there is a need for a method of path-capacity adaptation that takes into account the disparity in propagation delays between the edge nodes and the core nodes. In particular, a method is needed whereby the pace of reconfiguration of a core node is adapted so that a core node reconfigures more frequently to satisfy requests from close edge nodes without disturbing paths from distant edge nodes.